package algorithms.question.class18;

import common.util.MyUtil;

/**
 * 给定一个数组arr，长度为N，arr中的值只有1，2，3三种
 * arr[i] == 1，代表汉诺塔问题中，从上往下第i个圆盘目前在左
 * arr[i] == 2，代表汉诺塔问题中，从上往下第i个圆盘目前在中
 * arr[i] == 3，代表汉诺塔问题中，从上往下第i个圆盘目前在右
 * 那么arr整体就代表汉诺塔游戏过程中的一个状况
 * 如果这个状况不是汉诺塔最优解运动过程中的状况，返回-1
 * 如果这个状况是汉诺塔最优解运动过程中的状况，返回它是第几个状况
 *
 * @author guichang
 * @date 2021/8/16
 */

@SuppressWarnings("all")
public class Code1_汉诺塔最优解运动 {
    // arr[i] 在中间直接返回-1
    // arr[i] 在左边的话就表示只有arr[i-1]仅走了一步，1-2
    // arr[i] 在右边的话就表示arr[i-1]走完了三步，1-2 1-3 2-3

    public static void main(String[] args) {
//        int[] arr = {3, 2, 1}; // 2
        int[] arr = {3, 1, 1}; // 2
        MyUtil.print(step(arr));
    }

    public static int step(int[] arr) {
        return process(arr, arr.length - 1, 1, 3, 2);
    }

    /**
     * 当前来到了第i号圆盘，所在的位置from，要去的目的to，其他的位置other
     */
    private static int process(int[] arr, int i, int from, int to, int other) {
        if (i < 0) {
            return 0;
        }
        // 当前圆盘不可能在other
        if (arr[i] == other) {
            return -1;
        }
        // 当前圆盘还在from的话表示前i-1个圆盘移动了一步
        if (arr[i] == from) {
            return process(arr, i - 1, from, other, to);
        }
        // 当前圆盘在to的话表示一趟已经移动完毕
        // n个汉诺塔移动完毕最少要移动 2^n -1，此处要计算上一个场景也就是2^(n-1) -1，而n=i+1，所以结果是2^i -1
        int p1 = (1 << i) - 1;
        int p2 = 1; // i从from直接移动到to
        int p3 = process(arr, i - 1, other, to, from); // 前i-1个从other到to
        return p3 == -1 ? -1 : (p1 + p2 + p3);
    }


}